package com.yoshino.leetcode.interview150.stack;

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public boolean isValid(String s) {
        int length = s.length();
        if (length % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        char[] chars = new char[length];
        int ind = 0;
        for (int i = 0; i < length; i++) {
            if (ind == 0) {
                if (map.containsKey(s.charAt(i))) {
                    return false;
                } else {
                    chars[ind++] = s.charAt(i);
                }
            } else if (map.containsKey(s.charAt(i))) {
                ind--;
                if (!map.get(s.charAt(i)).equals(chars[ind])) {
                    return false;
                }
            } else {
                chars[ind++] = s.charAt(i);
            }
        }
        return ind == 0;
    }

    public String simplifyPath(String path) {
        Deque<String> res = new LinkedList<>();
        for (String s : path.split("/")) {
            if (s.equals("..") && !res.isEmpty()) {
                res.removeLast();
            } else if (!s.equals("") && !s.equals(".") && !s.equals("..")) {
                res.addLast(s);
            }
        }
        return "/" + res.stream().collect(Collectors.joining("/"));
    }

    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.addLast(stack.pollLast() + stack.pollLast());
                    break;
                case "-":
                    int f = stack.pollLast();
                    int s = stack.pollLast();
                    stack.addLast(s - f);
                    break;
                case "*":
                    stack.addLast(stack.pollLast() * stack.pollLast());
                    break;
                case "/":
                    int first = stack.pollLast();
                    int second = stack.pollLast();
                    stack.addLast(second / first);
                    break;
                default:
                    stack.addLast(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }

    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int length = s.length();
        int res = 0, sign = 1;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                // 多位数
                int cur = c - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1))) {
                    cur = cur * 10 + s.charAt(++i) - '0';
                }
                res = res + sign * cur;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                stack.addLast(res);
                res = 0;
                stack.addLast(sign);
                sign = 1;
            } else if (c == ')') {
                res = stack.pollLast() * res + stack.pollLast();
            }
        }
        return res;
    }
}